home *** CD-ROM | disk | FTP | other *** search
/ Cobra Utilities for Doom & Doom II / Cobra Utilities For Doom & Doom II - Disc 2.iso / files / program / ibsp101s / savecnct.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-10  |  15.0 KB  |  678 lines
  1. /* saveconnect.m */
  2.  
  3. #include "idbsp.h"
  4.  
  5. typedef struct
  6.     {
  7.     int                 x,
  8.                         y;
  9.     }
  10.  
  11. bpoint_t;
  12.  
  13. typedef struct
  14.     {
  15.     int                 xl,
  16.                         xh,
  17.                         yl,
  18.                         yh;
  19.     }
  20.  
  21. bbox_t;
  22.  
  23. typedef struct
  24.     {
  25.     bpoint_t            p1,
  26.                         p2;
  27.     }
  28. bline_t;
  29.  
  30. typedef struct
  31.     {
  32.     int                 numpoints;
  33.     bbox_t              bounds;
  34.     bpoint_t           *points;
  35.     }
  36.  
  37. bchain_t;
  38.  
  39. typedef struct
  40.     {
  41.     int                 x,
  42.                         y;
  43.     int                 dx,
  44.                         dy;
  45.     }
  46.  
  47. bdivline_t;
  48.  
  49.  
  50. /* [numsec][numsec] array */
  51. byte               *connections;
  52.  
  53. int                 numblines;
  54. bline_t            *blines;
  55.  
  56. int                 numsectors;
  57. bbox_t             *secboxes;
  58.  
  59. int                 numbchains;
  60. bchain_t           *bchains;
  61.  
  62. void                ClearBBox(bbox_t * box)
  63. {
  64.     box -> xl = box -> yl = INT_MAX;
  65.     box -> xh = box -> yh = INT_MIN;
  66. }
  67.  
  68. void                AddToBBox(bbox_t * box, int x, int y)
  69. {
  70.     if (x < box -> xl)
  71.         box -> xl = x;
  72.     if (x > box -> xh)
  73.         box -> xh = x;
  74.     if (y < box -> yl)
  75.         box -> yl = y;
  76.     if (y > box -> yh)
  77.         box -> yh = y;
  78. }
  79.  
  80.  
  81. /*
  82.    ==================
  83.    =
  84.    = BPointOnSide
  85.    =
  86.    = Returns side 0 (front), 1 (back), or -1 (colinear)
  87.    ==================
  88.  */
  89.  
  90. int                 BPointOnSide(bpoint_t * pt, bdivline_t * l)
  91. {
  92.     int                 dx,
  93.                         dy;
  94.     int                 left,
  95.                         right;
  96.  
  97.     if (!l -> dx)
  98.         {
  99.         if (pt -> x < l -> x)
  100.             return l -> dy > 0;
  101.         return l -> dy < 0;
  102.         }
  103.     if (!l -> dy)
  104.         {
  105.         if (pt -> y < l -> y)
  106.             return l -> dx < 0;
  107.         return l -> dx > 0;
  108.         }
  109.  
  110.  
  111.     dx = pt -> x - l -> x;
  112.     dy = pt -> y - l -> y;
  113.  
  114.     left = l -> dy * dx;
  115.     right = dy * l -> dx;
  116.  
  117.     if (right < left)
  118.         return 0;                       /* front side */
  119.     return 1;                           /* back side */
  120. }
  121.  
  122.  
  123. void                DrawBBox(bbox_t * box)
  124. {
  125. /*
  126.    PSmoveto (box->xl,box->yl);
  127.    PSlineto (box->xh,box->yl);
  128.    PSlineto (box->xh,box->yh);
  129.    PSlineto (box->xl,box->yh);
  130.    PSlineto (box->xl,box->yl);
  131.    PSstroke ();
  132.    NXPing ();
  133.  */
  134. }
  135.  
  136. void                DrawDivline(bdivline_t * li)
  137. {
  138. /*
  139.    PSmoveto (li->x,li->y);
  140.    PSrlineto (li->dx,li->dy);
  141.    PSstroke ();
  142.    NXPing ();
  143.  */
  144. }
  145.  
  146. void                DrawBChain(bchain_t * ch)
  147. {
  148. /*
  149.    int      i;
  150.  
  151.    PSmoveto (ch->points->x,ch->points->y);
  152.    for (i=1 ; i<ch->numpoints ; i++)
  153.    PSlineto (ch->points[i].x,ch->points[i].y);
  154.    PSstroke ();
  155.    NXPing ();
  156.  */
  157. }
  158.  
  159.  
  160. bdivline_t          ends[2],
  161.                     sides[2];
  162. int                 end0out,
  163.                     end1out,
  164.                     side0out,
  165.                     side1out;
  166. bbox_t              sweptarea;
  167.  
  168.  
  169. /*
  170.    ====================
  171.    =
  172.    = DoesChainBlock
  173.    =
  174.    ====================
  175.  */
  176.  
  177. boolean             DoesChainBlock(bchain_t * chain)
  178. {
  179. /*
  180.  
  181.    if a solid line can be walked from one side to the other without going out
  182.    an end, the path is blocked
  183.  
  184.  */
  185.  
  186.     bpoint_t           *pt;
  187.     int                 side,
  188.                         startside;
  189.     int                 p;
  190.  
  191. /* don't check if bounds don't intersect */
  192.  
  193.     if (sweptarea.xl > chain -> bounds.xh || sweptarea.xh < chain -> bounds.xl ||
  194.         sweptarea.yl > chain -> bounds.yh || sweptarea.yh < chain -> bounds.yl)
  195.         return false;
  196.  
  197.     startside = -1;                       /* not started yet */
  198.  
  199.     for (p = 0, pt = chain -> points; p < chain -> numpoints; p++, pt++)
  200.         {
  201.         /* find side for pt */
  202.  
  203. #if 0
  204.         if (p > 0)
  205.             {
  206.             PSmoveto((pt - 1) -> x, (pt - 1) -> y);
  207.             PSlineto(pt -> x, pt -> y);
  208.             PSstroke();
  209.             NXPing();
  210.             }
  211. #endif
  212.  
  213.         if (BPointOnSide(pt, &ends[0]) == end0out)
  214.             {
  215.             startside = -1;               /* off end */
  216.             continue;
  217.             }
  218.         if (BPointOnSide(pt, &ends[1]) == end1out)
  219.             {
  220.             startside = -1;               /* off end */
  221.             continue;
  222.             }
  223.         if (BPointOnSide(pt, &sides[0]) == side0out)
  224.             side = 0;
  225.         else if (BPointOnSide(pt, &sides[1]) == side1out)
  226.             side = 1;
  227.         else
  228.             continue;                   /* in middle */
  229.  
  230.         /* point is on one side or the other */
  231.         if (startside == -1 || startside == side)
  232.             {
  233.             startside = side;
  234.             continue;
  235.             }
  236.  
  237.         /* opposite of startside */
  238.         return true;                   /* totally crossed area */
  239.  
  240.         }
  241.  
  242.     return false;
  243. }
  244.  
  245. /*
  246.    ====================
  247.    =
  248.    = BuildConnections
  249.    =
  250.    ====================
  251.  */
  252.  
  253. enum
  254. {
  255.     si_north, si_east, si_south, si_west
  256. };
  257.  
  258. void                BuildConnections(void)
  259. {
  260.     int                 blockcount,
  261.                         passcount;
  262.     int                 i,
  263.                         j,
  264.                         k,
  265.                         s,
  266.                         bn;
  267.     int                 x,
  268.                         y;
  269.     bbox_t             *bbox[2];
  270.     int                 walls[4];
  271.     bpoint_t            points[2][2];
  272.  
  273. /* look for obscured sectors */
  274.     blockcount = passcount = 0;
  275.     bbox[0] = secboxes;
  276.     printf("\n");
  277.     for (i = 0; i < numsectors - 1; i++, bbox[0]++)
  278.         {
  279.         printf("connection #%d of %d\r", i, numsectors - 1);
  280.         bbox[1] = bbox[0] + 1;
  281.         if (bbox[0] -> xh - bbox[0] -> xl < 64 || bbox[0] -> yh - bbox[0] -> yl < 64)
  282.             {                           /* don't bother with small sectors (stairs, doorways, etc) */
  283.             continue;
  284.             }
  285.  
  286.         for (j = i + 1; j < numsectors; j++, bbox[1]++)
  287.             {
  288.             if (bbox[1] -> xh - bbox[1] -> xl < 64 || bbox[1] -> yh - bbox[1] -> yl < 64)
  289.                 {                       /* don't bother with small sectors (stairs, doorways, etc) */
  290.                 continue;
  291.                 }
  292.             if (bbox[1] -> xl <= bbox[0] -> xh && bbox[1] -> xh >= bbox[0] -> xl &&
  293.                 bbox[1] -> yl <= bbox[0] -> yh && bbox[1] -> yh >= bbox[0] -> yl)
  294.                 {                       /* touching sectors are never blocked */
  295.                 passcount++;
  296.                 continue;
  297.                 }
  298.  
  299.             sweptarea.xl = bbox[0] -> xl < bbox[1] -> xl ? bbox[0] -> xl : bbox[1] -> xl;
  300.             sweptarea.xh = bbox[0] -> xh > bbox[1] -> xh ? bbox[0] -> xh : bbox[1] -> xh;
  301.             sweptarea.yl = bbox[0] -> yl < bbox[1] -> yl ? bbox[0] -> yl : bbox[1] -> yl;
  302.             sweptarea.yh = bbox[0] -> yh > bbox[1] -> yh ? bbox[0] -> yh : bbox[1] -> yh;
  303.  
  304. /*
  305.    calculate the swept area between the sectors
  306.  */
  307.             for (bn = 0; bn < 2; bn++)
  308.                 {
  309.                 memset(walls, 0, sizeof(walls));
  310.                 if (bbox[bn] -> xl <= bbox[!bn] -> xl)
  311.                     walls[si_west] = 1;
  312.                 if (bbox[bn] -> xh >= bbox[!bn] -> xh)
  313.                     walls[si_east] = 1;
  314.                 if (bbox[bn] -> yl <= bbox[!bn] -> yl)
  315.                     walls[si_south] = 1;
  316.                 if (bbox[bn] -> yh >= bbox[!bn] -> yh)
  317.                     walls[si_north] = 1;
  318.  
  319.                 for (s = 0; s < 5; s++)
  320.                     {
  321.                     switch (s & 3)
  322.                         {
  323.                         case si_north:
  324.                         x = bbox[bn] -> xl;
  325.                         y = bbox[bn] -> yh;
  326.                         break;
  327.                         case si_east:
  328.                         x = bbox[bn] -> xh;
  329.                         y = bbox[bn] -> yh;
  330.                         break;
  331.                         case si_south:
  332.                         x = bbox[bn] -> xh;
  333.                         y = bbox[bn] -> yl;
  334.                         break;
  335.                         case si_west:
  336.                         x = bbox[bn] -> xl;
  337.                         y = bbox[bn] -> yl;
  338.                         break;
  339.                         }
  340.                     if (!walls[(s - 1) & 3] && walls[s & 3])
  341.                         {
  342.                         points[bn][0].x = x;
  343.                         points[bn][0].y = y;
  344.                         }
  345.                     if (walls[(s - 1) & 3] && !walls[s & 3])
  346.                         {
  347.                         points[bn][1].x = x;
  348.                         points[bn][1].y = y;
  349.                         }
  350.                     }
  351.  
  352.                 ends[bn].x = points[bn][0].x;
  353.                 ends[bn].y = points[bn][0].y;
  354.                 ends[bn].dx = points[bn][1].x - points[bn][0].x;
  355.                 ends[bn].dy = points[bn][1].y - points[bn][0].y;
  356.                 }
  357.  
  358.             sides[0].x = points[0][0].x;
  359.             sides[0].y = points[0][0].y;
  360.             sides[0].dx = points[1][1].x - points[0][0].x;
  361.             sides[0].dy = points[1][1].y - points[0][0].y;
  362.  
  363.             sides[1].x = points[0][1].x;
  364.             sides[1].y = points[0][1].y;
  365.             sides[1].dx = points[1][0].x - points[0][1].x;
  366.             sides[1].dy = points[1][0].y - points[0][1].y;
  367.  
  368.             end0out = !BPointOnSide(&points[1][0], &ends[0]);
  369.             end1out = !BPointOnSide(&points[0][0], &ends[1]);
  370.             side0out = !BPointOnSide(&points[0][1], &sides[0]);
  371.             side1out = !BPointOnSide(&points[0][0], &sides[1]);
  372.  
  373. /*
  374.    look for a line change that covers the swept area
  375.  */
  376.             for (k = 0; k < numbchains; k++)
  377.                 {
  378.                 if (!DoesChainBlock(&bchains[k]))
  379.                     continue;
  380.                 blockcount++;
  381.                 connections[i * numsectors + j] = connections[j * numsectors + i] = 1;
  382. /*
  383.    if (draw)
  384.    {
  385.    EraseWindow ();
  386.    DrawBBox (bbox[0]);
  387.    DrawBBox (bbox[1]);
  388.    DrawDivline (&ends[0]);
  389.    DrawDivline (&ends[1]);
  390.    DrawDivline (&sides[0]);
  391.    DrawDivline (&sides[1]);
  392.    DrawBChain (&bchains[k]);
  393.    }
  394.  */
  395.                 goto blocked;
  396.                 }
  397.  
  398. /* nothing definately blocked the path */
  399.             passcount++;
  400.           blocked:;
  401.             }
  402.         }
  403.     printf("passcount: %i\nblockcount: %i\n", passcount, blockcount);
  404. }
  405.  
  406.  
  407. /*
  408.    ====================
  409.    =
  410.    = BuildBlockingChains
  411.    =
  412.    ====================
  413.  */
  414.  
  415. void                BuildBlockingChains(void)
  416. {
  417.     boolean            *used;
  418.     int                 i,
  419.                         j;
  420.     bpoint_t           *temppoints,
  421.                        *pt_p;
  422.     bline_t            *li1,
  423.                        *li2;
  424.  
  425. /*  id          chains_i; */
  426.     STORAGE            *chains_i;
  427.     bchain_t            bch;
  428.     int                 cx,
  429.                         cy;
  430.  
  431.     used = alloca(numblines * sizeof(*used));
  432.     memset(used, 0, numblines * sizeof(*used));
  433.     temppoints = alloca(numblines * sizeof(*temppoints));
  434. /*
  435.    chains_i = [[Storage alloc]
  436.    initCount:       0
  437.    elementSize: sizeof(bchain_t)
  438.    description: NULL];
  439.  */
  440.     chains_i = (STORAGE *) SafeMalloc(sizeof(STORAGE));
  441.     chains_i -> data = (bchain_t *) SafeMalloc(sizeof(bchain_t));
  442.     chains_i -> count = 0;
  443.     chains_i -> size = sizeof(bchain_t);
  444.  
  445.     printf("\n");
  446.     li1 = blines;
  447.     for (i = 0; i < numblines; i++, li1++)
  448.         {
  449.         printf("bline #%d of %d\r", i, numblines);
  450.         if (used[i])
  451.             continue;
  452.         used[i] = true;
  453.  
  454.         /* start a new chain */
  455.         pt_p = temppoints;
  456.         pt_p -> x = li1 -> p1.x;
  457.         pt_p -> y = li1 -> p1.y;
  458.         pt_p++;
  459.         pt_p -> x = cx = li1 -> p2.x;
  460.         pt_p -> y = cy = li1 -> p2.y;
  461.         pt_p++;
  462.  
  463.         ClearBBox(&bch.bounds);
  464.         AddToBBox(&bch.bounds, li1 -> p1.x, li1 -> p1.y);
  465.         AddToBBox(&bch.bounds, cx, cy);
  466.  
  467.         /* look for connected lines */
  468.         do
  469.             {
  470.             li2 = li1 + 1;
  471.             for (j = i + 1; j < numblines; j++, li2++)
  472.                 if (!used[j] && li2 -> p1.x == cx && li2 -> p1.y == cy)
  473.                     break;
  474.  
  475.             if (j == numblines)
  476.                 break;                   /* no more lines in chain */
  477.  
  478.             /* add to chain */
  479.             used[j] = true;
  480.             pt_p -> x = cx = li2 -> p2.x;
  481.             pt_p -> y = cy = li2 -> p2.y;
  482.             pt_p++;
  483.             AddToBBox(&bch.bounds, cx, cy);
  484.             }
  485.         while (1);
  486.  
  487. /* save the block chain */
  488.         bch.numpoints = pt_p - temppoints;
  489.         bch.points = (bpoint_t *) malloc(bch.numpoints * sizeof(*bch.points));
  490.         memcpy(bch.points, temppoints, bch.numpoints * sizeof(*bch.points));
  491. /*      [chains_i addElement: &bch]; */
  492.         memcpy((bchain_t *) chains_i -> data + chains_i -> count, &bch, sizeof(bchain_t));
  493.         chains_i -> count += 1;
  494.         chains_i -> data = (bchain_t *) realloc(chains_i -> data,
  495.             sizeof(bchain_t) * (chains_i -> count + 1));
  496. /*DrawBChain (&bch); */
  497.         }
  498.  
  499. /*
  500.    numbchains = [chains_i count];
  501.    bchains = [chains_i elementAt:0];
  502.  */
  503.     numbchains = chains_i -> count;
  504.     bchains = chains_i -> data;
  505. }
  506.  
  507.  
  508. /*
  509.    ====================
  510.    =
  511.    = ProcessConnections
  512.    =
  513.    ====================
  514.  */
  515.  
  516. void                ProcessConnections(void)
  517. {
  518.     int                 i,
  519.                         s,
  520.                         wlcount,
  521.                         count;
  522.     bbox_t             *secbox;
  523.  
  524. /*  id                  lines; */
  525.     STORAGE            *lines;
  526.     worldline_t        *wl;
  527.     mapvertex_t        *vt;
  528.     maplinedef_t       *p;
  529.     mapsidedef_t       *sd;
  530.     bline_t             bline;
  531.     int                 sec;
  532.     int                 RonsLines = 0;
  533.  
  534. /*
  535.    numsectors = [secstore_i count];
  536.    wlcount = [linestore_i count];
  537.  */
  538.  
  539.     numsectors = secstore_i -> count;
  540.     wlcount = linestore_i -> count;
  541.  
  542.     connections = (unsigned char *)malloc(numsectors * numsectors + 8);        /* allow rounding to bytes */
  543.     memset(connections, 0, numsectors * numsectors);
  544.  
  545.     secboxes = secbox = (bbox_t *) malloc(numsectors * sizeof(bbox_t));
  546.     for (i = 0; i < numsectors; i++, secbox++)
  547.         ClearBBox(secbox);
  548.  
  549. /*
  550.    calculate bounding boxes for all sectors
  551.  
  552.    count = [ldefstore_i count];
  553.    p = [ldefstore_i elementAt:0];
  554.    vt = [mapvertexstore_i elementAt:0];
  555.  */
  556.  
  557.     count = ldefstore_i -> count;
  558.     p = ldefstore_i -> data;
  559.     vt = mapvertexstore_i -> data;
  560.     printf("\n");
  561.     for (i = 0; i < count; i++, p++)
  562.         {
  563.         printf("BBox #%d of %d\r", i, count);
  564.         for (s = 0; s < 1; s++)
  565.             {
  566.             if (p -> sidenum[s] == -1)
  567.                 continue;               /* no back side */
  568.             /* add both points to sector bounding box */
  569. /*      sd = (mapsidedef_t *)[sdefstore_i elementAt: p->sidenum[s]]; */
  570.             sd = (mapsidedef_t *) sdefstore_i -> data + p -> sidenum[s];
  571.             sec = sd -> sector;
  572.             AddToBBox(&secboxes[sec], vt[p -> v1].x, vt[p -> v1].y);
  573.             AddToBBox(&secboxes[sec], vt[p -> v2].x, vt[p -> v2].y);
  574.             }
  575.         }
  576.  
  577. /*
  578.    make a list of only the solid lines
  579.  */
  580. /*
  581.    lines = [[Storage alloc]
  582.    initCount:       0
  583.    elementSize: sizeof(bline)
  584.    description: NULL];
  585.  */
  586. /*
  587.    lines = SafeMalloc(sizeof(STORAGE));
  588.    lines->data = SafeMalloc(sizeof(bline));
  589.    lines->count = 0;
  590.    lines->size = sizeof(bline);
  591.  */
  592.  
  593. /*  wl = [linestore_i elementAt: 0]; */
  594.     printf("\n");
  595.     wl = linestore_i -> data;
  596.     for (i = 0; i < wlcount; wl++, i++)
  597.         {
  598.         if (wl -> flags & ML_TWOSIDED)
  599.             continue;
  600.         RonsLines++;
  601.         }
  602.  
  603.     lines = (STORAGE *) SafeMalloc(sizeof(STORAGE));
  604.     lines -> data = (bline_t *) SafeCalloc(RonsLines, sizeof(bline));
  605.     lines -> count = 0;
  606.     lines -> size = sizeof(bline);
  607.  
  608.     wl = linestore_i -> data;
  609.     for (i = 0; i < wlcount; wl++, i++)
  610.         {
  611.         printf("Line #%d of %d\r", i, wlcount);
  612.         if (wl -> flags & ML_TWOSIDED)
  613.             continue;                   /* don't add two sided lines */
  614.         bline.p1.x = wl -> p1.x;
  615.         bline.p1.y = wl -> p1.y;
  616.         bline.p2.x = wl -> p2.x;
  617.         bline.p2.y = wl -> p2.y;
  618. /*      [lines addElement: &bline]; */
  619.         memcpy((bline_t *) lines -> data + lines -> count, &bline, sizeof(bline));
  620.         lines -> count += 1;
  621. /*
  622.    lines->data = (bline_t *)realloc(lines->data,
  623.    sizeof(bline_t) + (lines->count + 1));
  624.  */
  625.         }
  626.  
  627. /*
  628.    blines = [lines elementAt: 0];
  629.    numblines = [lines count];
  630.  */
  631.  
  632.     blines = lines -> data;
  633.     numblines = lines -> count;
  634.  
  635. /*
  636.    build blocking chains
  637.  */
  638.     printf("\nBuildBlockingChains\n");
  639.     BuildBlockingChains();
  640.  
  641. /*
  642.    build connection list
  643.  */
  644.     printf("\nBuildConnections\n");
  645.     BuildConnections();
  646. }
  647.  
  648.  
  649. /*
  650.    =================
  651.    =
  652.    = OutputConnections
  653.    =
  654.    =================
  655.  */
  656.  
  657. void                OutputConnections(void)
  658. {
  659.     int                 i;
  660.     int                 bytes;
  661.     char               *cons;
  662.     char               *bits;
  663.  
  664.     cons = connections;
  665.     bytes = (numsectors * numsectors + 7) / 8;
  666.     bits = (char *)malloc(bytes);
  667.  
  668.     for (i = 0; i < bytes; i++)
  669.         {
  670.         bits[i] = cons[0] + (cons[1] << 1) + (cons[2] << 2) + (cons[3] << 3) + (cons[4] << 4) + (cons[5] << 5) + (cons[6] << 6) + (cons[7] << 7);
  671.         cons += 8;
  672.         }
  673.  
  674. /*  [wad_i addName: "reject" data:bits size:bytes]; */
  675.     addName("reject", bits, bytes);
  676.     printf("reject: %i\n", bytes);
  677. }
  678.